/**
 * @param {number[]} nums
 * @param {number} begin
 * @param {number} end
 */
function subSort(nums, begin, end) {
  if (begin >= end) return;
  const base = nums[begin];
  let left = begin;
  let right = end;
  while (left < right) {
    while (left < right && nums[right] >= base) {
      right -= 1;
    }
    while (left < right && nums[left] <= base) {
      left += 1;
    }
    const temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
  }
  nums[begin] = nums[left];
  nums[left] = base;
  subSort(nums, begin, left - 1);
  subSort(nums, left + 1, end);
}

/**
 * @description 快排（升序）
 * @param {number[]} nums
 */
function quickSort(nums) {
  subSort(nums, 0, nums.length - 1);
}

let src;
let answer;
let mine;
try {
  for (let i = 0; i < 1e3; i += 1) {
    const length = Math.floor(1e3 * Math.random());
    src = new Array(length).fill(0);
    for (let j = 0; j < length; j += 1) {
      src[j] = Math.round(1e3 * Math.random());
    }
    answer = [...src];
    answer.sort((a, b) => a - b);
    mine = [...src];
    quickSort(mine);
    if (answer.join() !== mine.join()) {
      throw new Error();
    }
  }
  console.log('测试通过');
} catch (e) {
  console.error('发现错误');
}
